/**
 * 
 */
package No201_300.No221_230.KthSmallestElementinaBST_230;

import java.util.Stack;

import jdk.nashorn.internal.runtime.regexp.joni.SearchAlgorithm;

/** 
 * @author  作者 E-mail: ttljtw@qq.com
 * @date 创建时间：2017年3月4日 下午8:03:30 
 * @version 1.0 
 * @parameter  
 * @since  
 * @return  
 */
/**
 * @author 李敬
 * 
 */
public class Solution {
	/*
	 * Kth Smallest Element in a BST
	 * */

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	static int ret;
	static int i;
	public int kthSmallest(TreeNode root, int k) {//递归方法
		ret = 0;i = 0;
		search(root,k);
		return ret;
	}
	private void search(TreeNode root,int k) {
		// TODO Auto-generated method stub
		if (root == null) {
			return;
		}else {
			search(root.left,k);
			i++;
			if(i == k) {
				ret = root.val;
				return;
			}
			search(root.right,k);
		}
		
	}


	public int kthSmallest1(TreeNode root, int k) {//非递归深搜方法需要牢记
		int[] a = new int[k];
		int i = 0;
		Stack<TreeNode> s = new Stack<>();
		while (i < k) {
			while (root != null) {
				s.push(root);
				root = root.left;
			}
			if (!s.empty()) {
				TreeNode temp = s.pop();
				a[i++] = temp.val;
				root = temp.right;
			} else {
				break;
			}
		}
		return a[k - 1];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
